﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Graph
{
    class AlgorithmFlow
    {
		private DirectGraph graph;
        private List<FlowKnoten> activeNodes = new List<FlowKnoten>();
        private DirectGraph residualGraph;
        public AlgorithmFlow(DirectGraph Graph)
        {
            graph = Graph;
            residualGraph = new DirectGraph();
            Dictionary<int, Knoten>.Enumerator KnotenEnumertor = graph.V.GetEnumerator();
            while (KnotenEnumertor.MoveNext())
            {
                FlowKnoten Knoten = new FlowKnoten(KnotenEnumertor.Current.Value.Id);
                residualGraph.neuerKnoten(Knoten);
            }
            KnotenEnumertor = graph.V.GetEnumerator();
            while (KnotenEnumertor.MoveNext())
            {
                Dictionary<int, List<Kante>>.Enumerator KantenEnumerator = graph.EOut[KnotenEnumertor.Current.Value.Id].GetEnumerator();
                while (KantenEnumerator.MoveNext())
                {
                    for (int i = 0; i < KantenEnumerator.Current.Value.Count; i++)
                    {
                        FlowKante Kante = new FlowKante(KantenEnumerator.Current.Value[i].Von, KantenEnumerator.Current.Value[i].Nach, KantenEnumerator.Current.Value[i].Gewicht, 0);
                        residualGraph.neueKante(Kante, KantenEnumerator.Current.Value[i].Gewicht);
                        Kante = new FlowKante(KantenEnumerator.Current.Value[i].Nach, KantenEnumerator.Current.Value[i].Von, KantenEnumerator.Current.Value[i].Gewicht, KantenEnumerator.Current.Value[i].Gewicht);
                        residualGraph.neueKante(Kante, KantenEnumerator.Current.Value[i].Gewicht);
                    }
                }
            }
        }

        public double getMaxFlowFIFO(int s, int t, bool GapHeuristic)
        {
            //PerProcessing----------
            double Flow = 0;
            List<int>[] GapArray = new List<int>[residualGraph.N * 2];
            if (GapHeuristic)
                for (int i = 0; i < GapArray.Length; i++)
                {
                    GapArray[i] = new List<int>();
                }

            Dictionary<int, List<Kante>>.Enumerator KantenEnumerator = residualGraph.EOut[s].GetEnumerator();
            while (KantenEnumerator.MoveNext())
            {
                for (int i = 0; i < KantenEnumerator.Current.Value.Count; i++)
                {
                    ((FlowKante)KantenEnumerator.Current.Value[i]).Fluss = ((FlowKante)KantenEnumerator.Current.Value[i]).Gewicht;
                    ((FlowKante)residualGraph.EOut[KantenEnumerator.Current.Value[i].Nach][KantenEnumerator.Current.Value[i].Von][i]).Fluss = 0;
                    if (residualGraph.V[KantenEnumerator.Current.Value[i].Nach].Id != t)
                    {
                        activeNodes.Add((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[i].Nach]);
                        activeNodes[activeNodes.Count - 1].Excess = ((FlowKante)KantenEnumerator.Current.Value[i]).Fluss;
                    }
                }
            }

            ((FlowKnoten)residualGraph.V[t]).Height = 0;

            List<int> BFSKnoten = new List<int>();
            BFSKnoten.Add(t);
            while (BFSKnoten.Count != 0)
            {
                KantenEnumerator = residualGraph.EOut[BFSKnoten[0]].GetEnumerator();
                int KnotenAbstand = ((FlowKnoten)residualGraph.V[BFSKnoten[0]]).Height;
                while (KantenEnumerator.MoveNext())
                {
                    if (((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[0].Nach]).Height < 0)
                    {
                        BFSKnoten.Add(KantenEnumerator.Current.Value[0].Nach);
                        ((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[0].Nach]).Height = KnotenAbstand + 1;
                    }
                }
                BFSKnoten.RemoveAt(0);
            }
            
            ((FlowKnoten)residualGraph.V[s]).Height = residualGraph.N;
            

            if (GapHeuristic)
            {
                for (int i = 0; i < residualGraph.V.Count; i++)
                {
                    if (i != s && i != t)
                        GapArray[((FlowKnoten)residualGraph.V[i]).Height].Add(residualGraph.V[i].Id);
                }
                //GapArray[residualGraph.N].Add(s);
            }

            //----------------------------

            while (activeNodes.Count != 0)
            {
                // Push
                KantenEnumerator = residualGraph.EOut[activeNodes[0].Id].GetEnumerator();
                while (activeNodes[0].Excess > 0 && KantenEnumerator.MoveNext())
                {
                    for (int i = 0; i < KantenEnumerator.Current.Value.Count; i++)
                    {
                        if (((FlowKante)KantenEnumerator.Current.Value[i]).Gewicht - ((FlowKante)KantenEnumerator.Current.Value[i]).Fluss > 0 &&
                            activeNodes[0].Height > ((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[i].Nach]).Height)
                        {
                             // Überschuss berechnen und eventuell zu aktiven Knoten hinzufügen
                            double min = Math.Min(activeNodes[0].Excess, ((FlowKante)residualGraph.EOut[KantenEnumerator.Current.Value[i].Nach][activeNodes[0].Id][i]).Fluss);
                            double FlussAenderung = min;// -((FlowKante)KantenEnumerator.Current.Value[0]).Fluss;
                            ((FlowKante)KantenEnumerator.Current.Value[i]).Fluss += min;
                            ((FlowKante)residualGraph.EOut[KantenEnumerator.Current.Value[i].Nach][KantenEnumerator.Current.Value[i].Von][i]).Fluss -= min;
                            activeNodes[0].Excess -= FlussAenderung;
                            ((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[i].Nach]).Excess += FlussAenderung;

                            if (((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[i].Nach]).Excess > 0 &&
                               !activeNodes.Contains(((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[i].Nach])) &&
                                residualGraph.V[KantenEnumerator.Current.Value[i].Nach].Id != s && residualGraph.V[KantenEnumerator.Current.Value[i].Nach].Id != t)
                                activeNodes.Add((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[i].Nach]);
                        }
                    }
                }


                // Relabel
                // h(v) ← min{h(w) + 1 | (v, w) ∈ E(x)}                
                if (activeNodes[0].Excess > 0)
                {
                    int minHeight = int.MaxValue;
                    KantenEnumerator = residualGraph.EOut[activeNodes[0].Id].GetEnumerator();
                    while (KantenEnumerator.MoveNext())
                    {
                        for (int i = 0; i < KantenEnumerator.Current.Value.Count; i++)
                        {
                            if (KantenEnumerator.Current.Value[i].Gewicht - ((FlowKante)KantenEnumerator.Current.Value[i]).Fluss > 0 && (((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[i].Nach]).Height + 1) < minHeight)
                                minHeight = ((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[i].Nach]).Height + 1;
                        }
                    }
                    if(GapHeuristic)
                    {
                        GapArray[activeNodes[0].Height].Remove(activeNodes[0].Id);
                        GapArray[minHeight].Add(activeNodes[0].Id);
                        activeNodes[0].Height = minHeight;     

                        if (GapArray[activeNodes[0].Height].Count == 0)
                        {
                            List<int> BFSKnotenInGap = new List<int>();
                            BFSKnotenInGap.Add(activeNodes[0].Id);
                            bool[] besucht = new bool[residualGraph.N];
                            while (BFSKnotenInGap.Count != 0)
                            {
                                KantenEnumerator = residualGraph.EOut[BFSKnotenInGap[0]].GetEnumerator();
                                int KnotenAbstand = ((FlowKnoten)residualGraph.V[BFSKnotenInGap[0]]).Height;
                                while (KantenEnumerator.MoveNext())
                                {
                                    if (!besucht[KantenEnumerator.Current.Value[0].Nach] && KantenEnumerator.Current.Value[0].Nach != s && KantenEnumerator.Current.Value[0].Nach != t)
                                    {
                                        besucht[KantenEnumerator.Current.Value[0].Nach] = true;
                                        BFSKnotenInGap.Add(KantenEnumerator.Current.Value[0].Nach);
                                        GapArray[((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[0].Nach]).Height].Remove(KantenEnumerator.Current.Value[0].Nach);
                                        GapArray[residualGraph.N].Add(KantenEnumerator.Current.Value[0].Nach);
                                        ((FlowKnoten)residualGraph.V[KantenEnumerator.Current.Value[0].Nach]).Height = residualGraph.N;
                                    }
                                }
                                BFSKnotenInGap.RemoveAt(0);
                            }
                        }
                        else
                            activeNodes[0].Height = minHeight;     
                    }
                    else
                    activeNodes[0].Height = minHeight;                    

                    FlowKnoten tmp = activeNodes[0];
                    activeNodes.RemoveAt(0);
                    activeNodes.Add(tmp);
                }
                else
                    activeNodes.RemoveAt(0);

            }
            Flow = ((FlowKnoten)residualGraph.V[t]).Excess;
            return Flow;
        }
    }
}
